home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / russell / gc32.lha / misc.c < prev    next >
C/C++ Source or Header  |  1993-07-20  |  13KB  |  460 lines
  1. /* 
  2.  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
  3.  * Copyright (c) 1991-1993 by Xerox Corporation.  All rights reserved.
  4.  *
  5.  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
  6.  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
  7.  *
  8.  * Permission is hereby granted to copy this garbage collector for any purpose,
  9.  * provided the above notices are retained on all copies.
  10.  */
  11.  
  12. #define DEBUG       /* Some run-time consistency checks */
  13. #undef DEBUG
  14. #define VERBOSE
  15. #undef VERBOSE
  16.  
  17. #include <stdio.h>
  18. #include <signal.h>
  19. #define I_HIDE_POINTERS    /* To make GC_call_with_alloc_lock visible */
  20. #include "gc_private.h"
  21.  
  22. # ifdef THREADS
  23. #   ifdef PCR
  24. #     include "pcr/il/PCR_IL.h"
  25.       struct PCR_Th_MLRep GC_allocate_ml;
  26. #   else
  27.     --> declare allocator lock here
  28. #   endif
  29. # endif
  30.  
  31. struct _GC_arrays GC_arrays = { 0 };
  32.  
  33. /* Initialize GC_obj_kinds properly and standard free lists properly.      */
  34. /* This must be done statically since they may be accessed before     */
  35. /* GC_init is called.                            */
  36. struct obj_kind GC_obj_kinds[MAXOBJKINDS] = {
  37. /* PTRFREE */ { &GC_aobjfreelist[0], &GC_areclaim_list[0],
  38.         GC_no_mark_proc, FALSE },
  39. /* NORMAL  */ { &GC_objfreelist[0], &GC_reclaim_list[0],
  40.         GC_normal_mark_proc, TRUE },
  41. /* UNCOLLECTABLE */
  42.           { &GC_uobjfreelist[0], &GC_ureclaim_list[0],
  43.         GC_normal_mark_proc, TRUE },
  44. # ifdef STUBBORN_ALLOC
  45. /*STUBBORN*/ { &GC_sobjfreelist[0], &GC_sreclaim_list[0],
  46.         GC_normal_mark_proc, TRUE },
  47. # endif
  48. };
  49.  
  50. # ifdef STUBBORN_ALLOC
  51.   int GC_n_kinds = 4;
  52. # else
  53.   int GC_n_kinds = 3;
  54. # endif
  55.  
  56. bool GC_debugging_started = FALSE;
  57.     /* defined here so we don't have to load debug_malloc.o */
  58.  
  59. void (*GC_check_heap)() = (void (*)())0;
  60.  
  61. ptr_t GC_stackbottom = 0;
  62.  
  63. word GC_hincr;
  64.  
  65. bool GC_dont_gc = 0;
  66.  
  67. bool GC_quiet = 0;
  68.  
  69. extern signed_word GC_mem_found;
  70.  
  71. # ifdef MERGE_SIZES
  72.     /* Set things up so that GC_size_map[i] >= words(i),        */
  73.     /* but not too much bigger                        */
  74.     /* and so that size_map contains relatively few distinct entries     */
  75.     /* This is stolen from Russ Atkinson's Cedar quantization        */
  76.     /* alogrithm (but we precompute it).                */
  77.  
  78.  
  79.     void GC_init_size_map()
  80.     {
  81.     register unsigned i;
  82.     register unsigned sz_rounded_up = 0;
  83.  
  84.     /* Map size 0 to 1.  This avoids problems at lower levels. */
  85.       GC_size_map[0] = 1;
  86.     /* One word objects don't have to be 2 word aligned.       */
  87.       for (i = 1; i < sizeof(word); i++) {
  88.           GC_size_map[i] = 1;
  89.       }
  90.       GC_size_map[sizeof(word)] = ROUNDED_UP_WORDS(sizeof(word));
  91.     for (i = sizeof(word) + 1; i <= 8 * sizeof(word); i++) {
  92. #           ifdef ALIGN_DOUBLE
  93.           GC_size_map[i] = (ROUNDED_UP_WORDS(i) + 1) & (~1);
  94. #           else
  95.           GC_size_map[i] = ROUNDED_UP_WORDS(i);
  96. #           endif
  97.     }
  98.     
  99.     for (i = 8*sizeof(word)+1; i <= WORDS_TO_BYTES(MAXOBJSZ); i++) {
  100.         if (sz_rounded_up < ROUNDED_UP_WORDS(i)) {
  101.             register int size = ROUNDED_UP_WORDS(i);
  102.                 register unsigned m = 0;
  103.             
  104.                 while (size > 7) {
  105.                   m += 1;
  106.                   size += 1;
  107.                   size >>= 1;
  108.                 }
  109.             sz_rounded_up = size << m;
  110.         if (sz_rounded_up > MAXOBJSZ) {
  111.             sz_rounded_up = MAXOBJSZ;
  112.         }
  113.         }
  114.         GC_size_map[i] = sz_rounded_up;
  115.     }
  116.     }
  117. # endif
  118.  
  119. /*
  120.  * The following is a gross hack to deal with a problem that can occur
  121.  * on machines that are sloppy about stack frame sizes, notably SPARC.
  122.  * Bogus pointers may be written to the stack and not cleared for
  123.  * a LONG time, because they always fall into holes in stack frames
  124.  * that are not written.  We partially address this by randomly clearing
  125.  * sections of the stack whenever we get control.
  126.  */
  127. word GC_stack_last_cleared = 0;    /* GC_no when we last did this */
  128. # define CLEAR_SIZE 213
  129. # define CLEAR_THRESHOLD 10000
  130. # define DEGRADE_RATE 50
  131.  
  132. ptr_t GC_min_sp;    /* Coolest stack pointer value from which we've */
  133.             /* already cleared the stack.            */
  134.             
  135. # ifdef STACK_GROWS_DOWN
  136. #   define COOLER_THAN >
  137. #   define HOTTER_THAN <
  138. #   define MAKE_COOLER(x,y) if ((word)(x)+(y) > (word)(x)) {(x) += (y);} \
  139.                 else {(x) = (ptr_t)ONES;}
  140. #   define MAKE_HOTTER(x,y) (x) -= (y)
  141. # else
  142. #   define COOLER_THAN <
  143. #   define HOTTER_THAN >
  144. #   define MAKE_COOLER(x,y) if ((word)(x)-(y) < (word)(x)) {(x) -= (y);} else {(x) = 0;}
  145. #   define MAKE_HOTTER(x,y) (x) += (y)
  146. # endif
  147.  
  148. ptr_t GC_high_water;
  149.             /* "hottest" stack pointer value we have seen    */
  150.             /* recently.  Degrades over time.        */
  151. /*ARGSUSED*/
  152. void GC_clear_stack_inner(d)
  153. word *d;
  154. {
  155.     word dummy[CLEAR_SIZE];
  156.     
  157.     bzero((char *)dummy, (int)(CLEAR_SIZE*sizeof(word)));
  158. #   ifdef THREADS
  159.       GC_noop(dummy);
  160. #   else
  161.         if ((ptr_t)(dummy) COOLER_THAN GC_min_sp) {
  162.             GC_clear_stack_inner(dummy);
  163.         }
  164. #   endif
  165. }
  166.  
  167. void GC_clear_stack()
  168. {
  169.     word dummy;
  170.  
  171.  
  172. # ifdef THREADS
  173.     GC_clear_stack_inner(&dummy);
  174. # else
  175.     if (GC_gc_no > GC_stack_last_cleared) {
  176.         /* Start things over, so we clear the entire stack again */
  177.         if (GC_stack_last_cleared == 0) GC_high_water = GC_stackbottom;
  178.         GC_min_sp = GC_high_water;
  179.         GC_stack_last_cleared = GC_gc_no;
  180.     }
  181.     /* Adjust GC_high_water */
  182.         MAKE_COOLER(GC_high_water, WORDS_TO_BYTES(DEGRADE_RATE));
  183.         if ((word)(&dummy) HOTTER_THAN (word)GC_high_water) {
  184.             GC_high_water = (ptr_t)(&dummy);
  185.         }
  186.     if ((word)(&dummy) COOLER_THAN (word)GC_min_sp) {
  187.         GC_clear_stack_inner(&dummy);
  188.         GC_min_sp = (ptr_t)(&dummy);
  189.     }
  190. # endif
  191. }
  192.  
  193.  
  194. /* Return a pointer to the base address of p, given a pointer to a    */
  195. /* an address within an object.  Return 0 o.w.                */
  196. # ifdef __STDC__
  197.     extern_ptr_t GC_base(extern_ptr_t p)
  198. # else
  199.     extern_ptr_t GC_base(p)
  200.     extern_ptr_t p;
  201. # endif
  202. {
  203.     register word r;
  204.     register struct hblk *h;
  205.     register hdr *candidate_hdr;
  206.     
  207.     r = (word)p;
  208.     h = HBLKPTR(r);
  209.     candidate_hdr = HDR(r);
  210.     if (candidate_hdr == 0) return(0);
  211.     /* If it's a pointer to the middle of a large object, move it    */
  212.     /* to the beginning.                        */
  213.     while (IS_FORWARDING_ADDR_OR_NIL(candidate_hdr)) {
  214.        h = h - (int)candidate_hdr;
  215.        r = (word)h + HDR_BYTES;
  216.        candidate_hdr = HDR(h);
  217.     }
  218.     if (candidate_hdr -> hb_map == GC_invalid_map) return(0);
  219.     /* Make sure r points to the beginning of the object */
  220.     r &= ~(WORDS_TO_BYTES(1) - 1);
  221.         {
  222.         register int offset =
  223.                 (word *)r - (word *)(HBLKPTR(r)) - HDR_WORDS;
  224.         register signed_word sz = candidate_hdr -> hb_sz;
  225.         register int correction;
  226.             
  227.         correction = offset % sz;
  228.         r -= (WORDS_TO_BYTES(correction));
  229.         if (((word *)r + sz) > (word *)(h + 1)
  230.             && sz <= BYTES_TO_WORDS(HBLKSIZE) - HDR_WORDS) {
  231.             return(0);
  232.         }
  233.     }
  234.     return((extern_ptr_t)r);
  235. }
  236.  
  237. /* Return the size of an object, given a pointer to its base.        */
  238. /* (For small obects this also happens to work from interior pointers,    */
  239. /* but that shouldn't be relied upon.)                    */
  240. # ifdef __STDC__
  241.     size_t GC_size(extern_ptr_t p)
  242. # else
  243.     size_t GC_size(p)
  244.     extern_ptr_t p;
  245. # endif
  246. {
  247.     register int sz;
  248.     register hdr * hhdr = HDR(p);
  249.     
  250.     sz = WORDS_TO_BYTES(hhdr -> hb_sz);
  251.     if (sz < 0) {
  252.         return(-sz);
  253.     } else {
  254.         return(sz);
  255.     }
  256. }
  257.  
  258. bool GC_is_initialized = FALSE;
  259.  
  260. void GC_init()
  261. {
  262.     DCL_LOCK_STATE;
  263.     
  264.     DISABLE_SIGNALS();
  265.     LOCK();
  266.     GC_init_inner();
  267.     UNLOCK();
  268.     ENABLE_SIGNALS();
  269.  
  270. }
  271.  
  272. void GC_init_inner()
  273. {
  274.     word dummy;
  275.     
  276.     if (GC_is_initialized) return;
  277.     GC_is_initialized = TRUE;
  278. #   ifndef THREADS
  279.       if (GC_stackbottom == 0) {
  280.     GC_stackbottom = GC_get_stack_base();
  281.       }
  282. #   endif
  283.     if  (sizeof (ptr_t) != sizeof(word)) {
  284.         GC_err_printf0("sizeof (ptr_t) != sizeof(word)\n");
  285.         ABORT("sizeof (ptr_t) != sizeof(word)\n");
  286.     }
  287.     if  (sizeof (signed_word) != sizeof(word)) {
  288.         GC_err_printf0("sizeof (signed_word) != sizeof(word)\n");
  289.         ABORT("sizeof (signed_word) != sizeof(word)\n");
  290.     }
  291.     if  (sizeof (struct hblk) != HBLKSIZE) {
  292.         GC_err_printf0("sizeof (struct hblk) != HBLKSIZE\n");
  293.         ABORT("sizeof (struct hblk) != HBLKSIZE\n");
  294.     }
  295. #   ifndef THREADS
  296. #     if defined(STACK_GROWS_UP) && defined(STACK_GROWS_DOWN)
  297.       GC_err_printf0(
  298.         "Only one of STACK_GROWS_UP and STACK_GROWS_DOWN should be defd\n");
  299.       ABORT("stack direction 1\n");
  300. #     endif
  301. #     if !defined(STACK_GROWS_UP) && !defined(STACK_GROWS_DOWN)
  302.       GC_err_printf0(
  303.         "One of STACK_GROWS_UP and STACK_GROWS_DOWN should be defd\n");
  304.       ABORT("stack direction 2\n");
  305. #     endif
  306. #     ifdef STACK_GROWS_DOWN
  307.         if ((word)(&dummy) > (word)GC_stackbottom) {
  308.           GC_err_printf0(
  309.               "STACK_GROWS_DOWN is defd, but stack appears to grow up\n");
  310.           GC_err_printf2("sp = 0x%lx, GC_stackbottom = 0x%lx\n",
  311.                       (unsigned long) (&dummy),
  312.                       (unsigned long) GC_stackbottom);
  313.           ABORT("stack direction 3\n");
  314.         }
  315. #     else
  316.         if ((word)(&dummy) < (word)GC_stackbottom) {
  317.           GC_err_printf0(
  318.               "STACK_GROWS_UP is defd, but stack appears to grow down\n");
  319.           GC_err_printf2("sp = 0x%lx, GC_stackbottom = 0x%lx\n",
  320.                           (unsigned long) (&dummy),
  321.                         (unsigned long) GC_stackbottom);
  322.           ABORT("stack direction 4");
  323.         }
  324. #     endif
  325. #   endif
  326. #   if !defined(_AUX_SOURCE) || defined(__GNUC__)
  327.       if ((word)(-1) < (word)0) {
  328.         GC_err_printf0("The type word should be an unsigned integer type\n");
  329.         GC_err_printf0("It appears to be signed\n");
  330.         ABORT("word");
  331.       }
  332. #   endif
  333.     if ((signed_word)(-1) >= (signed_word)0) {
  334.         GC_err_printf0(
  335.             "The type signed_word should be a signed integer type\n");
  336.         GC_err_printf0("It appears to be unsigned\n");
  337.         ABORT("signed_word");
  338.     }
  339.     
  340.     GC_hincr = HINCR;
  341.     GC_init_headers();
  342.     GC_bl_init();
  343.     GC_mark_init();
  344.     if (!GC_expand_hp_inner(GC_hincr)) {
  345.         GC_err_printf0("Can't start up: not enough memory\n");
  346.         EXIT();
  347.     }
  348.     /* Preallocate large object map.  It's otherwise inconvenient to     */
  349.     /* deal with failure.                        */
  350.       if (!GC_add_map_entry((word)0)) {
  351.         GC_err_printf0("Can't start up: not enough memory\n");
  352.         EXIT();
  353.       }
  354.     GC_register_displacement_inner(0L);
  355. #   ifdef MERGE_SIZES
  356.       GC_init_size_map();
  357. #   endif
  358.     /* Add initial guess of root sets */
  359.       GC_register_data_segments();
  360. #   ifdef PCR
  361.       PCR_IL_Lock(PCR_Bool_false, PCR_allSigsBlocked, PCR_waitForever);
  362.       PCR_IL_Unlock();
  363.       GC_pcr_install();
  364. #   endif
  365.     /* Get black list set up */
  366.       GC_gcollect_inner();
  367. #   ifdef STUBBORN_ALLOC
  368.         GC_stubborn_init();
  369. #   endif
  370.     /* Convince lint that some things are used */
  371. #   ifdef LINT
  372.       {
  373.           extern char * GC_copyright[];
  374.           extern GC_read();
  375.           
  376.           GC_noop(GC_copyright, GC_find_header, GC_print_block_list,
  377.                   GC_push_one, GC_call_with_alloc_lock, GC_read,
  378.                   GC_print_hblkfreelist, GC_dont_expand);
  379.       }
  380. #   endif
  381. }
  382.  
  383. void GC_enable_incremental()
  384. {
  385. # ifndef FIND_LEAK
  386.     DISABLE_SIGNALS();
  387.     LOCK();
  388.     if (!GC_is_initialized) {
  389.         GC_init_inner();
  390.     }
  391.     if (GC_words_allocd > 0) {
  392.         /* There may be unmarked reachable objects */
  393.         GC_gcollect_inner();
  394.     }   /* else we're OK in assumeing everything's */
  395.         /* clean since nothing can point to an       */
  396.         /* unmarked object.               */
  397.     GC_dirty_init();
  398.     GC_read_dirty();
  399.     GC_incremental = TRUE;
  400.     UNLOCK();
  401.     ENABLE_SIGNALS();
  402. # endif
  403. }
  404.  
  405. /* A version of printf that is unlikely to call malloc, and is thus safer */
  406. /* to call from the collector in case malloc has been bound to GC_malloc. */
  407. /* Assumes that no more than 1023 characters are written at once.      */
  408. /* Assumes that all arguments have been converted to something of the      */
  409. /* same size as long, and that the format conversions expect something      */
  410. /* of that size.                              */
  411. void GC_printf(format, a, b, c, d, e, f)
  412. char * format;
  413. long a, b, c, d, e, f;
  414. {
  415.     char buf[1025];
  416.     
  417.     if (GC_quiet) return;
  418.     buf[1024] = 0x15;
  419.     (void) sprintf(buf, format, a, b, c, d, e, f);
  420.     if (buf[1024] != 0x15) ABORT("GC_printf clobbered stack");
  421. #   ifdef OS2
  422.       /* We hope this doesn't allocate */
  423.       if (fwrite(buf, 1, strlen(buf), stdout) != strlen(buf))
  424.           ABORT("write to stdout failed");
  425. #   else
  426.       if (write(1, buf, strlen(buf)) < 0) ABORT("write to stdout failed");
  427. #   endif
  428. }
  429.  
  430. void GC_err_printf(format, a, b, c, d, e, f)
  431. char * format;
  432. long a, b, c, d, e, f;
  433. {
  434.     char buf[1025];
  435.     
  436.     buf[1024] = 0x15;
  437.     (void) sprintf(buf, format, a, b, c, d, e, f);
  438.     if (buf[1024] != 0x15) ABORT("GC_err_printf clobbered stack");
  439. #   ifdef OS2
  440.       /* We hope this doesn't allocate */
  441.       if (fwrite(buf, 1, strlen(buf), stderr) != strlen(buf))
  442.           ABORT("write to stderr failed");
  443. #   else
  444.       if (write(2, buf, strlen(buf)) < 0) ABORT("write to stderr failed");
  445. #   endif
  446. }
  447.  
  448. void GC_err_puts(s)
  449. char *s;
  450. {
  451. #   ifdef OS2
  452.       /* We hope this doesn't allocate */
  453.       if (fwrite(s, 1, strlen(s), stderr) != strlen(s))
  454.           ABORT("write to stderr failed");
  455. #   else
  456.       if (write(2, s, strlen(s)) < 0) ABORT("write to stderr failed");
  457. #   endif
  458. }
  459.  
  460.